package com.liuyi.usercenterservice.tools;

import com.liuyi.usercenterservice.entity.domain.User;

import java.util.List;

/**
 * @author 刘燚
 * @version v1.0.0
 * @Description 匹配算法
 * @createDate：2024/7/6 12:53
 * @email liuyia2022@163.com
 */
public class MatchUtils {
    /**
     * 用户匹配算法1 根据标签的相似度返回两个用户直接的相似度
     * 相似度 ： 在这指 tags 的标签变成 userTags 需要多少步
     * @param tags
     * @param userTags
     * @return
     */
    public static int minDistance(List<String> tags,List<String>  userTags){
        int n = tags.size();
        int m = userTags.size();

        if (n * m == 0) {
            return n + m;
        }
        // DP 数组
        int[][] D = new int[n + 1][m + 1];

        // 边界状态初始化
        for (int i = 0; i < n + 1; i++) {
            D[i][0] = i;
        }
        for (int j = 0; j < m + 1; j++) {
            D[0][j] = j;
        }
        // 计算所有 DP 值
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                int left = D[i - 1][j] + 1;
                int down = D[i][j - 1] + 1;
                int left_down = D[i - 1][j - 1];
                if (tags.get(i - 1).equals(userTags.get(j - 1))) {
                    left_down += 1;
                }
                D[i][j] = Math.min(left, Math.min(down, left_down));
            }
        }
        return D[n][m];
    }
}
